package 二叉树系列;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

public class IsSymmetric {
    public boolean isSymmetric(TreeNode root) {
        Deque<TreeNode> deque = new ArrayDeque<>();
        if(root==null) return true;
        deque.push(root);
        while(!deque.isEmpty()){
            int len = deque.size();
            Deque<TreeNode> temp = new LinkedList<>();
            for(int i=0;i<len;i++){
                TreeNode treeNode = deque.pollFirst();
                if(treeNode.left!=null){
                    deque.addLast(treeNode.left);
                    temp.addLast(treeNode.left);
                }else{
                    temp.addLast(null);
                }
                if(treeNode.right!=null) {
                    deque.addLast(treeNode.right);
                    temp.addLast(treeNode.right);
                }else {
                    temp.addLast(null);
                }
            }
            if(temp.size()%2!=0)   return false;
            int num = temp.size();
            for(int i=0;i<num/2;i++){
                if(temp.peekFirst()==null && temp.peekLast()==null){
                    temp.pollFirst();
                    temp.pollLast();
                    continue;
                }else if((temp.peekFirst()==null && temp.peekLast()!=null)||(temp.peekFirst()!=null && temp.peekLast()==null)){
                    return false;
                }
                System.out.println("i="+i);
                int i1 = temp.pollFirst().val;
                int i2 = temp.pollLast().val;
                if(i1!=i2){
                    return false;
                }
            }
        }
        return true;
    }
}
